1. Priority Claim
This application claims the benefit of priority from European Patent Application No. 06010675.4, filed May 23, 2006, which is incorporated here by reference in its entirety.
2. Technical Field
This invention relates to a system and method for indexing big word lists in databases. In particular, the invention relates to a system and method for indexing big word lists where sub-lists of data entries are indexed, and the sub-lists are further indexed.
3. Related Art
Navigation systems are increasingly prevalent in vehicles such as mid- and high-class automobiles. Navigation systems perform route guidance to a pre-determined destination input by a user. Such systems may verbally provide both route guidance and operation by the user using a speech control/recognition system or a display device.
Current navigation systems usually use large databases managed by a database management system that store lists of entries representing geographic data, such as cities, streets, points of interest, etc. These lists of entries may become very long for practical applications, for example, when the user uses the speech control recognition system or a tactile input device, such as a keyboard or touch-screen liquid crystal display. Consequently, management of these lists becomes difficult, especially when considering the limited computer resources available in navigation systems.
Current navigation systems often allow the user to choose from different entries of lists during separate operation stages. For example, in the route planning stage the navigation system may prompt the user to input a city and then a street name. The user may perform the input manually or verbally.
Usually, the lists are presented by displaying entries in alphabetical or lexicographic order. The user may scroll through displayed lists until he finds a desired entry. The user may then mark this entry or may directly input text using a keyboard, touch-screen LCD, or the speech-recognition system. Where the user uses the keyboard, the database management system will often perform an incremental search on the other entries in the list. The incremental search may require the input of only the first significant characters of an entire word, such as the name of a city the user wants to be guided to. Following unique characters may be automatically added.
In order to accelerate the selection process of geographical location, such as a city or a street, after the entry of one or more characters the navigation system may present the user the next characters of stored entries from which to choose. When the user has entered a predetermined amount of characters to identify a desired entry, the input may be automatically completed and the user may be prompted to confirm the identified entry.
In current navigation systems, databases may be indexed. Indexing may allow for faster database operations, such as selecting, deleting, and updating data entries. Indexing also may serve for sorting the data entries in lists. In traditional databases, indices are transparent to the application using the database. For example, during an index-supported search of the database by the navigation system, the navigation system is usually unable to access the indexed data contents.
Indices of a database are usually implemented as a tree structure, such as a binary tree, assuming a pre-defined sort order of the managed data. Alternatively, the indexing itself may establish a sort order. A search for an entry of a list may be performed in accordance with the implemented tree structure. Current methods of indexing use indices that range over all the data entries of a particular data class. For example, current methods may use indices that range over the entire set of city names or street names. Reference to sub-sets of the street names, such as street names corresponding to a particular city, may be made by using two-dimensional indices. This technique is generally known as column indexing. The first columns of an index may represent a city and the second column of an index may represent a street. Multi-column indices range over the entirety of data entries may be stored as different data types.
Additionally, indices may be used to calculate the remaining alphanumeric characters for a partial alphanumeric input previously entered by the user. Alternatively, the remaining alphanumeric characters may be calculated and stored in a predetermined tree structure.
However, current indexing techniques often lead to a huge data structure for each index that ranges over all the data entries for a data class stored in the database. Thus, where the computer and storage resources are rather limited, such as in current navigation systems, it is often difficult to transfer the entire index into a main memory. Information about possible characters following a partial alphanumeric input by the user may further require additional storage capacities and techniques, such as virtual memory and memory swapping. Access to these additional storage capacities and techniques during runtime of a search for a data entry often leads to an extensive computational load accompanied by delays in processing the user's input. Extensive computational loads and delays further lead to an undesirable waiting time by the user.
Accordingly, there is a need for a system and method for indexing entries in databases that allow for faster access to data entries. In addition, there is a need for a system and method that manages and recognizes data entries in data lists that works effectively where limited computer resources are available.